User blog:Nayuta Ito/Introduction to Taranovsky's Ordinal Notation
General Taranovsky's Ordinal Notation(TON) has infinite system: 0th, 1st, 2nd, 3rd, and so on. In the nth system, a 2-ary function symbol C, and two constant symbols, 0 and Ω_n, are used (In the 0th system, Ω_0=0 and only 0 is used). However, C does not "return" an ordinal; they can just be compared each other. But how? Here's how to compare TON notation: Write the notation and reverse the order of all the symbols. And compare it lexicographically assuming C<0. Note that you can only compare TONs from the same system because you can NOT compare Ω_1 and Ω_2 according to the definition. Here are some examples: C(0,C(0,0))C(C(W_1,0),0) because 0W_1C0C is lexicographically after 00W_1CC (W_1 is considered as one letter) C(W_2,0)>C(C(W_2,0),0) because 0W_2C is lexicographically after 00W_2CC (W_2 is considered as one letter) I will coin a word "lex" for the reversed order notation of TON shown above. 0th System In the 0th system, you can only use 0 and C. Before starting the analysis, we need to define the standard form. Here is the definition: 1. 0 is standard. 2. C(α,β) is standard if and only if: 2a. α and β are standard 2b. β=0 or β=C(γ,δ) with α<=γ For emample, C(C(0,0),0) is standard but C(C(0,0),C(0,0)) is not standard because C(0,0)<=0 is not true. Now consider the smallest ordinal expressible with the 0th system. When you consider about the order, you need to think with lex. Now let's see the smallest one. Can the lex start with C? No. Let's prove it by contradiction. If it were possible, the original notation would look like ...C, followed by only parentheses. But this is impossible because C is a 2-ary funtion symbol. Next, can we start the lex with 0? Yes! And the smallest one is "0", so it corresponds to the smallest ordinal, a.k.a. zero. Continuing the similar inference, you can get following: 0=0 C(0,0)=1 C(0,C(0,0))=2 C(0,C(0,C(0,0)))=3 C(C(0,0),0)=w C(0,C(C(0,0),0))=w+1 C(C(0,0),C(C(0,0),0))=w2 C(C(0,C(0,0)),0)=w^2 C(C(C(0,0),0),0)=w^w C(C(C(...C(C(0,0),0)...,0),0),0)=e_0 /w infinite C's Generally, the following holds in the 0th system: \( C(\alpha,\beta)=\beta+\omega^{\alpha} \). But now you might think, "How can I find the fundamental sequence of, say, C(C(0,C(0,0)),0)?" Well, a method was suggested for nth system but we're discussing its validity. There might be an easy one for the 0th system, but I don't know what it is. (Related to fundamental sequence, there exists a very easy way of checking if a TON expression is limit or not: C(0,anything) is successor and everything else is limit. I will leave the proof for readers' exercise because it is easy.) 1st System I will write Ω_1 as W because many people do so and it's easier to type and see. Before I explain the 1st system, I need to explain about "n-built from below (n-BFB) from". To explain BFB, I also need to explain "subterm", so I do. For any TON expression η, a η is subterm of η. If η=C(γ,δ), and ι is a subterm of γ or δ, ι is a subterm of η. However, this is an easy concept with examples. C(W,0) has subterm C(W,0), W, and 0 C(C(0,0),C(W,0)) has subterm C(C(0,0),C(W,0)), C(0,0), C(W,0), 0, and W Now you get the idea. Now I can explain BFB. Here is the definition: 1. α is 0-BFB from β if and only if α<β. 2. α is (k+1)-BFB from β if and only if: 2a. For all subterm γ of α, either of them follows: 2aa. γ<=α 2ab. there exists subterm δ of α such that γ is subterm of δ and δ is k-built from below from β. This is hard to explain, but intuitively, it's the "collapsing count" (Look at the figure, make more examples and try to understand it yourself). Finally we can define the standard form in the 1st system TON: 1. 0 and W are standard. 2. C(α,β) is standard if and only if: 2a. α and β are in standard form 2b. β = 0, or β = W, or β = C(γ,δ) with α ≤ γ 2c. α is 1-BFB from C(α,β) Basically the same as the 0th system, but the 1-BFB rule is added. If α<β, α is 1-BFB from β, therefore all the standard form in the 0th system is also standard in the 1st system. Let's check if C(W,0) is standard. In this case, we need to use the rule 2 because it has C at the start. So we need to check 2a to 2c. 2a: Both W and 0 are standard according to 1, so it's satisfied. 2b: β=0, so it's satisfied. 2c: Is W 1-BFB from C(W,0)? Let's check the definitions of BFB. Since W is not smaller than C(W,0), We need to go to 2a. The all subterm of W is only W and W<=W follows, so according to 2aa and letting k=0, W is 1-BFB from C(W,0). Therefore, C(W,0) is standard. Since this is the limit of the 0th system, it's ε_0 in a "normal" notation. Now something similar to 0th system happens at this point. The next ordinal of C(W,0)=ε_0 is C(0,C(W,0))=ε_0+1, then C(0,C(0,C(W,0)))=ε_0+2 comes, and after all that there is C(C(0,0),C(W,0))=ε_0+ω. Of course you can have C(C(W,0),C(W,0))=ε_0*2. You will continue like this: C(C(W,0),C(W,0))=ε_0*2 C(C(W,0),C(C(W,0),C(W,0)))=ε_0*3 C(C(0,C(W,0)),C(W,0))=ε_0*ω C(C(C(W,0),C(W,0)),C(W,0))=ε_0^2 C(C(C(0,C(W,0)),C(W,0)),C(W,0))=ε_0^ω C(C(C(C(W,0),C(W,0)),C(W,0)),C(W,0))=ε_0^ε_0 C(W,C(W,0))=ε_1 C(W,C(W,C(W,0)))=ε_2 C(C(0,W),0)=ε_ω Note that C(0,W) is the "next ordinal" of W, a.k.a. W+1. WIP 2nd System WIP 3rd System and higher We don't know what happens. Category:Blog posts